class Node {
    public int val;
    public Node next;//类型是Node null

    public Node(int val) {
        this.val = val;
    }
}

public class SingleLinkedList {
    public Node head;//定义到这是因为它是链表的头
    public int usedSize;//记录当前链表节点个数
    //穷举法创建链表
    public void createList() {
        Node node1 = new Node(12);
        Node node2 = new Node(23);
        Node node3 = new Node(34);
        Node node4 = new Node(45);
        Node node5 = new Node(56);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1;
        this.usedSize = 5;
    }
    //打印链表
    public void myToString() {
        Node cur = this.head;//不用head的原因是防止head最后指向空
        //循环条件不能为cur.next!=null,否则最后一个节点值不打印
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    //重载打印方法(从指定节点开始打印)
    public void myToString(Node newHead) {
        Node cur = newHead;
        //循环条件不能为cur.next!=null,否则最后一个节点值不打印
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    //查找是否包含关键字key在链表中
    public boolean contains(int key) {
        Node cur = this.head;
        while(cur!=null){
            //如果key不是整形，用equals比较
            if(cur.val==key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //得到单链表的长度(尝试不使用usedSize),如果使用usedSize直接返回即可(优点时间复杂度小)
    public int size() {
        Node cur = this.head;
        int num = 0;
        while(cur!=null){
            num++;
            cur = cur.next;
        }
        return num;
    }
    //头插法
    public void addFirst(int data) {
        Node node = new Node(data);
        if(this.head==null) {
            this.head = node;
        }else {
            node.next = this.head;
            this.head = node;
        }
        this.usedSize++;
    }
    //尾插法
    public void addLast(int data){
        Node node = new Node(data);
        if(this.head == null) {
            this.head = node;
        }else {
            Node cur = this.head;
            while (cur.next!=null) {
                cur = cur.next;
            }
            //cur指向最后一个节点
            cur.next = node;
        }
        this.usedSize++;
    }
    //查找index的前一个节点并返回
    public Node searchIndex(int index) {
        Node cur = head;
        for (int i = 0; i < index-1; i++) {
            cur = cur.next;
        }
        return cur;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data) {
        Node node = new Node(data);
        if(index<0||index>this.usedSize){
            throw new RuntimeException("index不合法!");
        }
        if(index == 0){
            addFirst(data);
            return;
        }
        if(index == this.usedSize){
            addLast(data);
            return;
        }
        Node cur = searchIndex(index);
        node.next = cur.next;
        cur.next = node;
        this.usedSize++;
    }
    //找到key关键字的前一个节点
    public Node searchKey(int key) {
        Node cur = this.head;
        while(cur.next!=null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key){
        //链表为空
        if(this.head == null) {
            return;
        }
        //头结点就是要求删除的节点
        if(this.head.val == key){
            this.head = this.head.next;
            this.usedSize--;
            return;
        }
        Node cur = searchKey(key);
        if(cur == null){
            throw new RuntimeException("不存在要删除的节点!");
        }
        Node del = cur.next;
        cur.next = del.next;
        this.usedSize--;
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(this.head == null){
            return;
        }
        Node cur = this.head.next;
        Node prev = this.head;
        while(cur!=null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
                this.usedSize--;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        if(this.head.val == key){
            this.head = this.head.next;
            this.usedSize--;
        }
    }
    //清空链表
    public void clear(){
        Node cur = this.head;
        while (cur!=null){
            Node curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        this.head = null;
        this.usedSize = 0;
    }
    public void clear1() {
        //暴力写法
        this.head = null;
        this.usedSize = 0;
    }

    //逆置链表
    public Node reverseList(Node head){
        if(this.head == null) {
            return null;
        }
        if(this.head.next == null) {
            return this.head;
        }
        //两个节点以上
        Node cur = this.head.next;
        this.head.next = null;
        while(cur!=null){
            Node curNext = cur.next;
            cur.next = this.head;
            this.head = cur;
            cur = curNext;
        }
        return this.head;
    }

    //求中间节点(快慢指针(快指针走满指针的2倍),只用遍历链表一遍)
    public Node middleNode() {
        if(this.head == null) {
            return null;
        }
        if(this.head.next == null) {
            return this.head;
        }
        Node fast = this.head;
        Node slow = this.head;
        while(fast!=null&&fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //找到单列表倒数k个节点
    public Node FindKthToTail(int k) {
        if(k<=0||this.head==null) {
            return null;
        }
        Node fast = this.head;
        Node slow = this.head;
        int count1 = 0;
        while(fast.next!=null){
            fast = fast.next;
            if(count1 >= k-1){
                slow = slow.next;
            }
            count1++;
        }
        if(count1 < k-1){
            return null;
        }
        return slow;
    }

    //分割链表
    public Node partition(int x) {
        Node bs = null;
        Node be = null;
        Node as = null;
        Node ae = null;
        Node cur = this.head;
        while(cur!=null){
            if(cur.val < x){
                //尾插法
                if(bs == null){
                    bs = cur;
                    be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
            }else{
                if(as == null){
                    as = cur;
                    ae = cur;
                }else{
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        if(bs == null) {
            return as;
        }
        be.next = as;
        //如果后面区段有数据,需要把最后一个节点的next置为空,否则会出现死循环
        if(as != null) {
            ae.next = null;
        }
        return bs;
    }

    //回文检查
    public boolean chkPalindrome() {
        if(this.head==null||this.head.next==null){
            return true;
        }
        //1.求中间节点
        Node fast = this.head;
        Node slow = this.head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //2.逆置右边节点
        Node cur = slow.next;
        while(cur!=null) {
            Node curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3.判断回文
        Node left = this.head;
        Node right = slow;
        while(left!=right){
            if(left.val!=right.val){
                return false;
            }else{
                left = left.next;
                right = right.next;
            }
            //偶数链表结束条件
            if(left.next==right) {
                return true;
            }
        }
        return true;
    }

    //判断链表是否有环
    public boolean hasCycle() {
        //此处判断可有可无
        if(this.head == null||this.head.next == null) {
            return false;
        }
        Node fast = this.head;
        Node slow = this.head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow) {
                return true;
            }
        }
        return false;
    }
    //求环的入口点
    public Node detectCycle() {
        Node fast = this.head;
        Node slow = this.head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow) {
                break;
            }
        }
        if(fast==null||fast.next==null) {
            return null;
        }
        //双指针一次走一步情况下,路程关系为head到公共节点的路程==相遇点到公共节点的路程+环的长度的n-1倍
        fast = this.head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}



